﻿#include<iostream>
using namespace std;
#include<vector>
#include<string>
#include <algorithm>

//在一些安全性要求较高的APP中，通常我们输入密码时，系统弹出的输入框都是乱序的。这样一来就能防止想通过观察手指点击位置来推测密码的坏人。
//
//现在小苯有一个可能乱序的九宫格按键，但他没注意到九宫格是乱序，因此他还是按照正常九宫格顺序点击的按键。
//（正常九宫格：也就是按照1 到9 分为三行三列，从上到下，从左到右都是递增的，下方备注有图）
//
//请你告诉他，在他点击完按键后，屏幕上显示的数字都应该是什么？
//int main()
//{
//	vector<int>arr, arr2;
//	for (int i = 0; i <= 9; ++i)
//	{
//		arr.push_back(i);
//	}
//	arr2.push_back(0);
//	for (int i = 1; i <= 9; ++i)
//	{
//		int num = 0;
//		cin >> num;
//		arr2.push_back(num);
//	}
//	string A;
//	cin >> A;
//	for (int i = 1; i <= A.size(); ++i)
//	{
//		int num = (A[i - 1] - '0');
//		cout << arr2[arr[num]];
//	}
//	return 0;
//
//大白熊给了小苯一个长度为n 的数组a，这次他希望小苯从数组中选择一个子序列（下方备注有定义解释），满足这个子序列构成的数组是一个“好数组”。
//大白熊定义好数组是：如果一个数组按升序排序后和原来不完全相同，则其是一个好数组。例如[3, 2, 2] 升序排序后是
//[2, 2, 3]，和原来不完全相同，因此是一个好数组，而[1, 2, 2] 不是一个好数组。
//
//小苯想知道，如果想要使得选择的子序列构成一个“好数组”，最长可以选多长的子序列？

//const int N = 2e5 + 10;
//int arr[N];
//int main()
//{
//	int n;
//	cin >> n;
//	int flag = 0;
//	cin >> arr[1];
//	for (int i = 2; i <= n; ++i)
//	{
//		cin >> arr[i];
//		if (arr[i] < arr[i - 1])
//		{
//			flag = 1;
//		}
//	}
//	if (flag)
//	{
//		cout << n << endl;//只要出现，就说明数组不是递增，那么整个数组就是好数组
//	}
//	else
//	{
//		cout << 0 <<endl;
//	}
//	return 0;
//}

//大白熊给了小苯一个长度为n 的数组a，小苯想要最大化a 的极差。具体的，小苯可以做如下操作任意次（前提是数组至少有两个数字）：
//∙ 选择一个正整数i(1≤i < n)，接着将ai与a(i + 1)
//	​
//合并为一个数字，结果为二者的和。
//（即：将ai变为ai+a(i+1)，然后删去a（i + 1），当然操作完后a 的长度也会减一。）
//
//小苯想知道他最大能将数组极差变为多少呢，请你帮帮他吧。

//#include <iostream>
//#include <vector>
//#include <algorithm>
//using namespace std;
//typedef long long ll;
//
//int main()
//{
//    int n;
//    cin >> n;
//    if (n == 1)
//    {
//        return 0;
//    }
//    vector<ll> a(n);
//    ll sum1 = 0, sum2 = 0;
//
//    for (int i = 0; i < n; ++i)
//    {
//        cin >> a[i];
//        sum1 += a[i];
//    }
//
//    vector<ll>dp(n);
//    dp[0] = sum1 - a[0] - a[0];
//    for (ll i = 1; i < n - 1; ++i)
//    {
//        sum2 += a[i - 1];
//        dp[i] = max(abs(sum2 - a[i]), abs(sum1 - sum2 - a[i] - a[i]));
//    }
//    dp[n - 1] = sum2 + a[n - 2] - a[n - 1];
//    cout << (*max_element(dp.begin(), dp.end()));
//
//    return 0;
//}